package algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 102. 二叉树的层序遍历
 * @author Panbo Guo
 * @date 2021/7/19
 */
public class T00102 {

    public static void main(String[] args) {
        Integer[] arr = new Integer[] {3,9,20,null,null,15,7};
        System.out.println(new Solution().levelOrder(TreeUtils.buildTree(arr)));
    }

    static class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            if (root != null) {
                // First floor
                ArrayList<Integer> firstFloor = new ArrayList<>();
                firstFloor.add(root.val);
                list.add(firstFloor);

                LinkedList<TreeNode> list1 = new LinkedList<>();
                LinkedList<TreeNode> list2 = new LinkedList<>();
                list1.add(root);
                while (!list1.isEmpty()) {
                    ArrayList<Integer> curFloor = new ArrayList<>();
                    do {
                        TreeNode head = list1.removeFirst();
                        if (head.left != null) {
                            list2.add(head.left);
                            curFloor.add(head.left.val);
                        }
                        if (head.right != null) {
                            list2.add(head.right);
                            curFloor.add(head.right.val);
                        }
                    } while (!list1.isEmpty());

                    if (!curFloor.isEmpty())
                        list.add(curFloor);

                    // Swap temp list
                    LinkedList<TreeNode> temp = list1;
                    list1 = list2;
                    list2 = temp;
                }
            }
            return list;
        }
    }
}
